A switch constituting a network decides, from the destination MAC address of an inputted frame, an output port through which the frame is to be outputted, before transmitting the frame. A destination decision unit in the switch performs destination decision processing for deciding the output port. The destination decision unit includes a forwarding data base that stores plural forwarding entries each consisting of a MAC address and a port number corresponding to the address. When a frame is inputted, the destination decision unit determines whether a destination MAC address in a header matches any of MAC addresses of forwarding entries, and decides a port number in a matching entry as the port number of an output port of the inputted frame. When there is no matching forwarding entry, the switch performs flooding to transmit the inputted frame to all output ports.
The destination decision unit performs address learning for creating a forwarding data base in addition to the destination decision processing. This processing compares a MAC address in a forwarding entry with a source MAC address in a header, and when there is no matching forwarding entry, registers the source MAC address in the header and a port number inputted by the inputted frame as a MAC address and a port number of the forwarding entry, respectively.
Rich Seifert, “LAN Switching Detailed Description” Nikkei BP Inc. describes a high speed destination decision method by use of CAM (Contents Addressable Memory), which is a device for fast search. CAM includes plural match conditions, and when a search key is inputted, determines whether the search key matches any of the plural match conditions. When a match condition exists, it outputs information related with the match condition, and when there is no match condition, outputs the information indicating that there is no match condition.
FIG. 18 is a conceptual diagram of a destination decision unit to which Rich Seifert, “LAN Switching Detailed Description” Nikkei BP Inc. is applied. In the destination decision unit in Rich Seifert, “LAN Switching Detailed Description” Nikkei BP Inc., as shown in FIG. 18, MAC addresses in the forwarding data base as match conditions, and output port numbers corresponding to those addresses as related information are stored in CAM 1801. When a frame is inputted, the CAM 1801 determines whether a destination MAC address in the frame matches any of MAC addresses as match conditions, and decides a port number corresponding to a matching match condition as an output port number through which the inputted frame is to be outputted. Also in address learning, to check for the existence of a forwarding entry matching a source MAC address, the source MAC address has only to be inputted to the CAM 1801 as a search key.
The switch may include a flow decision unit in addition to the destination decision unit. The flow decision unit performs flow decision processing that decides the flow to which a frame belongs from information in a header of the frame. The flow refers to a flow of frames with same particular header information. The flow decision unit has plural flow entries that each stores a flow condition consisting of combinations of different items of a frame header such as a source address and a destination address, and flow information corresponding to the flow condition. Flow control information may include any one, or two or more of filter information indicating frame transmission, QoS information indicating frame transmission priority, and statistics information. When a frame is inputted, the switch searches for a flow entry having a flow condition that matches information in the frame, and based on flow information of the matching entry, decides filter information, QoS information, and collects statistics.
According to a method described in V. Srinivasan, G. Varghese, S. Suri, M. Waldvogel, “Fast and Scalable Layer Four Switching”, Proceedings of ACM SIGCOMM '98, pp. 191-202, high speed flow decision processing called cross-producing is described. In this method, flow conditions are split into small field conditions such as destination address and source address. The flow decision processing determines for each field whether information in a header matches any of the split flow conditions, and based on individual comparison results, decides a finally matching flow entry. As a method of deciding a final flow entry, there is described a method for providing a cross product table that stores indication information of a flow entry to match among all possible combinations from the split flow conditions. For example, when the flow conditions consist of five fields and the respective numbers of split flow conditions are 4, 4, 5, 2, and 3, the number of pieces of indication information of matching flow entries is 480 (=4×4×5×2×3). V. Srinivasan, G. Varghese, S. Suri, M. Waldvogel, “Fast and Scalable Layer Four Switching”, Proceedings of ACM SIGCOMM '98, p 191-202 also describes “On-demand cross producing” that reduces the number of entries of the cross product table. This method sets entries of the cross product table on demand. When necessary entries exist in the cross product table, the same processing as the cross producing is performed. When no necessary entries exist in the cross product table, low-speed flow decision processing such as normal linear search is performed, and indication information corresponding to a processed packet is created in the cross product table.
Furthermore, in Uga, et. al. “Flow Identification Method by Use of Contents Addressable Memory” Institute Electronic, Information and Communication and Engineers, 2000 Comprehensive Convention Lecture Papers SB-4-2, a method for speeding up router's flow decision processing by use of TCAM (Ternary Contents Addressable Memory) is described. TCAM allows not only comparison of “0” and “1” for each bit of match conditions but also a comparison mask (wildcard) of “0” and “1” that indicates any information is permitted.
FIG. 19 is a conceptual diagram of a flow decision unit to which Uga, et. al. “Flow Identification Method by Use of Contents Addressable Memory” Institute Electronic, Information and Communication and Engineers, 2000 Comprehensive Convention Lecture Papers SB-4-2 is applied.
This method will be described below using the conceptual diagram of Uga et. al. “Flow Identification Method by Use of Contents Addressable Memory” Institute Electronic, Information and Communication and Engineers, 2000 Comprehensive Convention Lecture Papers SB-4-2. FIG. 19 shows TCAM 1901 that stores plural entries 1910-i (i=1 to N) describing flow conditions created by combinations of source address, destination address, and protocols, and a search result table 1902 that stores flow information 1920-i describing flow information corresponding to the entry 1910-i. “d.c” is a mask indicating that any information is permitted. When a frame is inputted, it is determined whether header information of a packet matches any of entries 1910-i, and based on flow information 1920-i corresponding to a matching entry 1910-i, filter information and QoS information are decided and statistics is collected.
Furthermore, JP-A No. 78549/2003 “Packet Transmission Method and Device” describes a flow decision method that reduces the number of set flow entries. For example, when a flow is decided for each destination address and for each source address, the number of flow entries required in the flow decision unit to which Uga et. al. “Flow Identification Method by Use of Contents Addressable Memory” Institute Electronic, Information and Communication and Engineers, 2000 Comprehensive Convention Lecture Papers SB-4-2 is applied is the product of the number of variations of destination addresses multiplied by the number of variations of source addresses. A flow decision unit described in JP-A No. 78549/2003 “Packet Transmission Method and Device” includes a flow decision unit of V. Srinivasan, G. Varghese, S. Suri, M. Waldvogel, “Fast and Scalable Layer Four Switching”, Proceedings of ACM SIGCOMM '98, p 191-202 as a previous-stage flow decision unit and a following-stage flow decision unit. TCAM of the previous-stage flow decision unit contains as many flow conditions as there are variations of destination addresses, wherein each of the flow conditions other than conditions of destination address is masked. TCAM of the following-stage flow decision unit contains the flow condition of the temporal flow number decided in the previous-stage flow decision unit, the flow condition of a source address, and flow conditions each of which is masked. When a frame is inputted, the previous-stage flow decision unit performs first flow decision processing according to header information of the input frame to decide the temporal flow number determined from only a destination address. The following-stage flow decision unit performs second flow decision processing to decide a final flow from the temporal flow number and the header information. The number of set flow entries is the sum of the number of variations of destination addresses and the number of variations of source addresses. Therefore, when the respective numbers of variations are large, the flow decision unit of JP-A No. 78549/2003 “Packet Transmission Method and Device” can reduce the number of flow entries set in the flow decision unit of V. Srinivasan, G. Varghese, S. Suri, M. Waldvogel, “Fast and Scalable Layer Four Switching”, Proceedings of ACM SIGCOMM '98, p 191-202.
The above-mentioned Uga et. al. “Flow Identification Method by Use of Contents Addressable Memory” Institute Electronic, Information and Communication and Engineers, 2000 Comprehensive Convention Lecture Papers SB-4-2 and Rich Seifert, “LAN Switching Detailed Description” Nikkei BP Inc. have a problem with low-cost achievement of both of the destination decision unit and the flow decision unit.
When Uga et. al. “Flow Identification Method by Use of Contents Addressable Memory” Institute Electronic, Information and Communication and Engineers, 2000 Comprehensive Convention Lecture Papers SB-4-2 and Rich Seifert, “LAN Switching Detailed Description” Nikkei BP Inc. are applied, the above-mentioned destination decision unit and the flow decision unit are required individually. In the CAM 1801 of the destination decision unit, all MAC addresses used for destination decision are set. In the TCAM 1901 of the flow decision unit, source MAC addresses and destination MAC addresses are respectively set as conditions of source addresses and destination addresses. In this case, identical MAC addresses may be set in the CAMs of the destination decision unit and the flow decision unit. For example, when a MAC address corresponding to a source address x and a destination address x of FIG. 19 is a MAC address x, a MAC address 1 and the like are set in the CAM 1801 and the TCAM 1901. Since the destination decision unit and the flow decision unit to which Uga et. al. “Flow Identification Method by Use of Contents Addressable Memory” Institute Electronic, Information and Communication and Engineers, 2000 Comprehensive Convention Lecture Papers SB-4-2 and V. Srinivasan, G. Varghese, S. Suri, M. Waldvogel, “Fast and Scalable Layer Four Switching”, Proceedings of ACM SIGCOMM '98, p 191-202 are applied must redundantly set MAC addresses having the long bit length of 48 bits, CAM capacity cannot be efficiently used. The wasteful use of CAM capacity causes an increase in the costs of the destination decision unit and the flow decision unit.
In TCAM of a flow decision unit to which JP-A No. 78549/2003 “Packet Transmission Method and Device” and Uga et. al. “Flow Identification Method by Use of Contents Addressable Memory” Institute Electronic, Information and Communication and Engineers, 2000 Comprehensive Convention Lecture Papers SB-4-2 are applied, masks of MAC addresses are set as flow conditions. In the flow decision unit of JP-A No. 78549/2003 “Packet Transmission Method and Device”, in the case where the pre-stage flow decision unit decides the temporal flow number by a source MAC address, and the following-stage flow decision unit decides a final flow based on a destination MAC address, a destination MAC address of a flow entry of the pre-stage flow decision unit and a source MAC address of a flow entry of the following-stage flow decision unit are masked. In the flow decision unit of Uga et. al. “Flow Identification Method by Use of Contents Addressable Memory” Institute Electronic, Information and Communication and Engineers, 2000 Comprehensive Convention Lecture Papers SB-4-2, masks indicated by d.c are set in the TCAM 1901 of FIG. 19. Since MAC addresses have the long bit length of 48 bits as described previously and CAM capacity becomes large, a more inexpensive flow decision unit can be achieved if the masks can be omitted.
In the case of V. Srinivasan, G. Varghese, S. Suri, M. Waldvogel, “Fast and Scalable Layer Four Switching”, Proceedings of ACM SIGCOMM '98, p 191-202, if only MAC address identification conditions are set in CAM, although masks and the conditions of duplicate MAC addresses do not need to be set, there is a problem in that a table that stores indication information of flow entries to match becomes large. When flow conditions consist of K fields and N flow entries exist, a maximum of NK pieces of indication information are required. For example, when the number of fields is 4 and the number of flow entries is 2048, 244 entries are required. Although the use of on-demand cross producing reduces the number of pieces of the indication information, there has been a problem in that flow decision processing slows down remarkably when a cross-product table has no entry.